def sort(l):  # 排序
    for i in range(len(l)):
        if i > len(l) - 1 - i:
            break
        x = l[i]
        l[i] = l[len(l) - 1 - i]
        l[len(l) - 1 - i] = x
    return l


def half(lis, left, right, k):  # 二分查找
    # lis=sort(lis)
    if left > right:
        return '没找到'
    mid = (left + right) // 2
    if lis[mid] == k:
        return '找到了, 位置:{}'.format(mid)
    else:
        if lis[mid] > k:
            right = mid - 1
        elif lis[mid] < k:
            left = mid + 1
        else:
            return mid
    return half(lis, left, right, k)


def halfcheck(lis, left, right, k): # 二分查找
    while 1:
        if left < right:
            mid = (left + right) // 2
            if k < lis[mid]:
                right -= 1
            elif k > lis[mid]:
                left += 1
            else:
                return '找到了, 位置:{}'.format(mid)
        else:
            return '没找到'


li = [1, 2, 3, 4, 5, 6, 7, 8, 9]
h = halfcheck(li, 0, len(li) - 1, 6)
print(h)
